package com.gitee.swsk33.algorithms.graph.admatrix;

import lombok.Getter;

import java.util.Arrays;

/**
 * 网-邻接矩阵
 * 矩阵存放弧的权值，若不连通则存放无穷大（Double.POSITIVE_INFINITY），若为无向网，则邻接矩阵对称
 */
public class ADMatrixNet<T> {

	/**
	 * 顶点集合
	 */
	private T[] vertexes;

	/**
	 * 邻接矩阵
	 */
	private double[][] matrix;

	/**
	 * 是否是有向网
	 */
	private boolean directed;

	/**
	 * 顶点数
	 */
	@Getter
	private int vertexCount;

	/**
	 * 弧的数量
	 */
	@Getter
	private int arcCount;

	/**
	 * 图-邻接矩阵构造函数
	 *
	 * @param vertexes 传入顶点数组以初始化图
	 * @param directed 定义这个网是否是有向网
	 */
	public ADMatrixNet(T[] vertexes, boolean directed) {
		this.vertexes = vertexes;
		this.directed = directed;
		vertexCount = vertexes.length;
		arcCount = 0;
		// 初始化邻接矩阵，默认都为无穷大
		matrix = new double[vertexCount][vertexCount];
		for (double[] line : matrix) {
			Arrays.fill(line, Double.POSITIVE_INFINITY);
		}
	}

	/**
	 * 获取一个顶点在图中顶点列表的下标
	 *
	 * @param vertex 传入一个顶点值
	 * @return 这个顶点在图中顶点列表的下标，若该顶点不存在返回-1
	 */
	public int getVertexIndex(T vertex) {
		for (int i = 0; i < vertexCount; i++) {
			if (vertex == vertexes[i]) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 获取一个顶点值
	 *
	 * @param index 顶点在图中的下标
	 * @return 对应顶点值
	 */
	public T getVertex(int index) {
		return vertexes[index];
	}

	/**
	 * 设定一个顶点的值
	 *
	 * @param index 要设定顶点的下标
	 * @param value 要设定的值
	 */
	public void setVertex(int index, T value) {
		vertexes[index] = value;
	}

	/**
	 * 添加一个弧
	 *
	 * @param indexStart 弧的起点的下标
	 * @param indexEnd   弧的终点的下标
	 * @param weight     弧的权值
	 */
	public void addArc(int indexStart, int indexEnd, double weight) {
		matrix[indexStart][indexEnd] = weight;
		if (!directed) {
			matrix[indexEnd][indexStart] = weight;
		}
		arcCount++;
	}

	/**
	 * 删除一个弧
	 *
	 * @param indexStart 弧的起点的下标
	 * @param indexEnd   弧的终点的下标
	 */
	public void deleteArc(int indexStart, int indexEnd) {
		matrix[indexStart][indexEnd] = Double.POSITIVE_INFINITY;
		if (!directed) {
			matrix[indexEnd][indexStart] = Double.POSITIVE_INFINITY;
		}
		arcCount--;
	}

	/**
	 * 获取一个弧的权值
	 *
	 * @param indexStart 弧的起点
	 * @param indexEnd   弧的终点
	 * @return 弧的权值
	 */
	public double getWeight(int indexStart, int indexEnd) {
		return matrix[indexStart][indexEnd];
	}

	/**
	 * 两个顶点是否连通
	 *
	 * @param indexStart 起点顶点下标
	 * @param indexEnd   终点顶点下标
	 * @return 起点和终点是否连通
	 */
	public boolean isConnect(int indexStart, int indexEnd) {
		return matrix[indexStart][indexEnd] != Double.POSITIVE_INFINITY;
	}

	/**
	 * 用于输出
	 */
	@Override
	public String toString() {
		StringBuilder result = new StringBuilder();
		for (double[] line : matrix) {
			for (double value : line) {
				if (value == Double.POSITIVE_INFINITY) {
					result.append("∞ ");
				} else {
					result.append(value).append(" ");
				}
			}
			result.append("\r\n");
		}
		return result.toString();
	}

}